package leetbook.dynamic_plan;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Solution329 {

    public static void main(String[] args) {

        int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
        System.out.println(new Solution329().longestIncreasingPath(matrix));
    }

    int res = 0;

    public int longestIncreasingPath1(int[][] matrix) {
        Stack<Integer> record = new Stack<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                backTrace(matrix,i,j,record);
            }
        }
        return res;
    }

    public void backTrace(int[][] matrix, int i, int j, Stack<Integer> record){
        //到达边界或者不满足条件(已访问过（设为-1）或者不满足严格递增)
        // TODO: 2021/8/10 并不会回头看已经访问过的，所以没必要加禁忌搜索
        if(i<0||i==matrix.length||j<0||j==matrix[0].length||
        !record.isEmpty()&&matrix[i][j]<=record.peek()){
            res = Math.max(res, record.size());
            return;
        }
        //探索
        record.push(matrix[i][j]);
        backTrace(matrix,i,j+1,record);
        backTrace(matrix,i+1,j,record);
        backTrace(matrix,i,j-1,record);
        backTrace(matrix,i-1,j,record);
        record.pop();
    }

    public int longestIncreasingPath(int[][] matrix) {

        int m = matrix.length, n = matrix[0].length;
        int[][] directs = {{0,1},{0,-1},{1,0},{-1,0}};
        //要按从小到大的顺序或者拓扑排序的顺序算dp
        //1.计算拓扑排序
        //1.1构建入度
        int[][] inDegree = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] drc:directs) {
                    int newi = i+drc[0], newj = j+drc[1];
                    if(newi>-1&&newi<m&&newj>-1&&newj<n){
                        if(matrix[i][j]>matrix[newi][newj]){
                            inDegree[i][j]++;
                        }
                    }
                }
            }
        }
        //1.2按拓扑排序入队
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        while (queue.size()<m*n){
            //寻找每一个入度为0的点
            int i = 0, j = 0;
            c:for (i = 0; i < m; i++) {
                for (j = 0; j < n; j++) {
                    if(!visited[i][j]&&inDegree[i][j]==0){
                        break c;
                    }
                }
            }
            //找到了，加入queue
            queue.offer(new int[]{i,j});
            visited[i][j] = true;
            //更新相邻节点的入度
            for (int[] drc:directs) {
                int newi = i+drc[0], newj = j+drc[1];
                if(newi>-1&&newi<m&&newj>-1&&newj<n){
                    if(matrix[i][j]<matrix[newi][newj]){
                        inDegree[newi][newj]--;
                    }
                }
            }
        }
        //2.按拓扑排序进行dp
        int[][] dp = new int[m][n];
        int max = 0;
        while (!queue.isEmpty()){
            int[] idx = queue.poll();
            int i = idx[0], j = idx[1], temp = 0;
            //计算以当前节点为尾巴的最长递增序列长度
            //dp[i][j] = max(dp[周围元素比matrix[i][j]小的那些])+1
            for (int[] drc:directs) {
                int newi = i+drc[0], newj = j+drc[1];
                if(newi>-1&&newi<m&&newj>-1&&newj<n){
                    if(matrix[i][j]>matrix[newi][newj]){
                        temp = Math.max(temp, dp[newi][newj]);
                    }
                }
            }
            dp[i][j] = temp+1;
            max = Math.max(max,dp[i][j]);
        }
        return max;
    }
}
